package com.example.leetcode.trainingcamp.week5.Sunday;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给你两个数组，arr1 和 arr2，
 *
 * <p>arr2 中的元素各不相同 arr2 中的每个元素都出现在 arr1 中 对 arr1 中的元素进行排序，使 arr1
 * 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 *
 * <p>
 *
 * <p>示例：
 *
 * <p>输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 输出：[2,2,2,1,4,3,3,9,6,7,19]
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/relative-sort-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test1122 {

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int value : arr1) {
            map.put(value, map.getOrDefault(value, 0) + 1);
        }
        int[] result = new int[arr1.length];
        int j = 0;
        for (int i:arr2){
            Integer integer = map.get(i);
            while (integer>0){
                result[j] = i;
                integer--;
                j++;
            }
            map.remove(i);
        }
        int[] t = new int[arr1.length - j];
        int t1 = 0;
        for (int key:map.keySet()){
            Integer integer = map.get(key);
            while (integer>0){
                t[t1] = key;
                t1++;
                integer--;
            }

        }
        Arrays.sort(t);
        System.arraycopy(t,0,result,j,t.length);
        return  result;
    }
}

//[2,42,38,0,43,21,5,7,12,12,13,23,24,24,27,29,30,31,33,48]
class Demo1122{
  public static void main(String[] args) {
    int[] arr1 = {2,21,43,38,0,42,33,7,24,13,12,27,12,24,5,23,29,48,30,31};
    int[] arr2 = {2,42,38,0,43,21};
    Test1122 t = new Test1122();
    int[] ints = t.relativeSortArray(arr1, arr2);
    for ( int i: ints) {
      System.out.print(i+",");
    }
  }
}